package 纯数组;

import java.util.LinkedList;

public class JZ62圆圈中最后剩下的数字 {

    /**
     * 0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，
     * 每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。
     * 求出这个圆圈里剩下的最后一个数字。
     * 例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，
     * 则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
     *
     * 示例 1：
     * 输入: n = 5, m = 3
     * 输出: 3
     * 示例 2：
     * 输入: n = 10, m = 17
     * 输出: 2
     *  
     * 限制：
     * 1 <= n <= 10^5
     * 1 <= m <= 10^6
     */

    /**
     * 优质解法: 倒推活下来的位置
     * 只看护每轮活下来的位置下标
     * 例子: 0,1,2,3,4,5,6  2
     * 0,1,2,3,4,5,6 ->活下标 6
     * 0,2,3,4,5,6   ->活下标 4
     * 0,2,3,4,5     ->活下标 2
     * 0,2,4,5       ->活下标 0
     * 0,2,4         ->活下标 2 (手动算在n=4,m=2的情况下)
     * 0,4           ->活下标 0 (手动算在n=3,m=2的情况下)
     * 4             ->活下标 0    |从这里开始往上推
     * 从下往上推,发现了规律。
     * f(1)=0;一个数时答案就是下标0;
     * f(2)=(f(1)+m)%i=(0+2)%2=0;
     * f(3)=(f(2)+m)%i=(0+2)%3=2;
     * f(4)=(f(3)+m)%i=(2+2)%4=0;
     * f(5)=(0+2)%5=2;
     * f(6)=(2+2)%6=4;
     * f(7)=(4+2)%7=6; 答案
     */
    public int lastRemaining(int n, int m) {

        int result=0;//最终的答案下标为0

        for (int i = 2; i <= n; i++) {
            result=(result+m)%i;
        }

        return result;
    }

    /**
     * 如果n很小,m很大,那么这样循环岂不是很浪费时间;
     * bad解法; 平庸做法: n^2做法是使用ArrayList,利用公式直接确定下标;
     */
    private class Node{
        public int value;
        public Node next;
        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    public int lastRemainingBad(int n, int m) {

        if(m==1){
            return n-1;
        }

        Node head=new Node(-1,null);
        Node cur=head;

        for (int i = 0; i < n; i++) {
            cur.next=new Node(i,null);
            cur=cur.next;
        }

        //连城环
        cur.next=head.next;

        Node last=null;
        cur=head.next;
        int index=0;
        int count=n;

        /**
         * 如果n很小,m很大,那么这样循环岂不是很浪费时间
         */
        while (count!=1){
            index++;
            if(index==m){
                //移除当前节点
                count--;
                Node temp=cur.next;
                last.next=cur.next;
                cur.next=null;
                cur=temp;
                index=0;
            }else {
                last = cur;
                cur = cur.next;
            }
        }

        return cur.value;
    }

    public static void main(String[] args) {
        JZ62圆圈中最后剩下的数字 jz=new JZ62圆圈中最后剩下的数字();
        int result = jz.lastRemainingBad(70866, 116922);
        System.out.println(result);
    }

}
